package middle;

public class Solution_416 {

    public static void main(String[] args) {
        Solution_416 model = new Solution_416();
        System.out.println(model.canPartition(new int[]{1,5,11,5}));
        System.out.println(model.canPartition(new int[]{1,2,3,5}));
        System.out.println(model.canPartition(new int[]{1}));
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        sum >>= 1;
        int[][] array = new int[nums.length + 1][sum + 1];
        for (int i = 1; i < array.length; i++) {
            for (int j = 1; j < array[i].length; j++) {
                if (nums[i - 1] <= j) {
                    array[i][j] = Math.max(nums[i - 1] + array[i-1][j - nums[i - 1]], array[i - 1][j]);
                } else {
                    array[i][j] = array[i - 1][j];
                }
            }
        }
        return array[nums.length][sum] == sum;
    }
}
